from typing import List


class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n = len(nums)

        sorted_keys = sorted(set(nums))
        m = len(sorted_keys)

        default = pow(10, 6) * n

        # 定义状态：dp[i][j][l] = 前i个字符、移动j次、当前值为k的最小浪费空间  dp[i][j][m] = 前i个字符、移动j次的最小浪费空间
        dp = [[[default] * (m + 1) for _ in range(k + 1)] for _ in range(n)]

        # 初始化dp[0]的状态
        for l in range(m):
            if sorted_keys[l] >= nums[0]:
                dp[0][0][l] = sorted_keys[l] - nums[0]
        dp[0][0][m] = 0

        # 状态转移
        for i in range(1, n):
            # 处理j=0的情况
            for l in range(m):
                if sorted_keys[l] >= nums[i]:
                    dp[i][0][l] = dp[i - 1][0][l] + (sorted_keys[l] - nums[i])
                    dp[i][0][m] = min(dp[i][0][m], dp[i][0][l])

            for j in range(1, k + 1):
                for l in range(m):
                    if sorted_keys[l] >= nums[i]:
                        dp[i][j][l] = min(dp[i - 1][j][l] + (sorted_keys[l] - nums[i]),  # 不修改数组大小
                                          dp[i - 1][j - 1][m] + (sorted_keys[l] - nums[i]))  # 改变数组大小
                        dp[i][j][m] = min(dp[i][j][m], dp[i][j][l])

        # for row in dp:
        #     print(row)

        return min(dp[-1][j][m] for j in range(k + 1))


if __name__ == "__main__":
    print(Solution().minSpaceWastedKResizing(nums=[10, 20], k=0))  # 10
    print(Solution().minSpaceWastedKResizing(nums=[10, 20, 30], k=1))  # 10
    print(Solution().minSpaceWastedKResizing(nums=[10, 20, 15, 30, 20], k=2))  # 15
